package _01_第一季.树04.Tree03;

import _01_第一季.树04.printer.BinaryTreeInfo;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/*
    二叉树的属性公共定义
 */
public class BinaryTree<E> implements BinaryTreeInfo{
    protected int size;
    protected Node<E> root;

    protected static class Node<E>{
        E element;
        Node<E> left;
        Node<E> right;
        Node<E> parent;

        public Node(){
            this(null,null);
        }
        public Node(E element,Node<E> parent){
            this.element = element;
            this.parent = parent;
        }
        public boolean isLeaf(){
            return left == null && right == null;
        }
        public boolean hasTwoKids(){
            return left!=null && right!=null;
        }
        public boolean isLeftChild(){
            return parent!=null && this == parent.left;
        }
        public boolean isRightChild(){
            return parent!=null && this == parent.right;
        }
        public Node<E> sibling(){
            if(isLeftChild()){
                return right;
            }
            if(isRightChild()){
                return left;
            }
            return null;
        }
    }

    /**
     * 为了让子类使用他们各自的节点类去构造节点，在父类写一个创建节点的接口，交给子类实现
     * @param element
     * @param parent
     * @return
     */
    protected Node<E> createNode(E element,Node<E> parent){
        return new Node<>(element,parent);
    }

    public int size(){
        return size;
    }

    public boolean isEmpty(){
        return size == 0;
    }

    public void clear(){
        root = null;
        size = 0;
    }

    //找到该节点的前驱节点:中序遍历时的前一个节点
    protected Node<E> predecessor(Node<E> node){
        Node<E> pre = node.left;
        if(pre!=null){
            while(pre.right!=null){
                pre = pre.right;
            }
            return pre;
        }

        while(node.parent!=null && node == node.parent.left){
            node = node.parent;
        }
        return node.parent;
    }

    //找到该节点的后继节点:中序遍历时的后一个节点
    protected Node<E> successor(Node<E> node){
        Node<E> s = node.right;
        if(s!=null){
            while(s.left!=null){
                s = s.left;
            }
            return s;
        }

        while(node.parent!=null && node == node.parent.right){
            node = node.parent;
        }
        return node.parent;
    }

    //判断是否是完全二叉树
    public boolean isComplete(){
        if(root == null) return false;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);

        boolean leaf = false; //默认不是叶子节点

        while(!queue.isEmpty()){
            Node<E> node = queue.poll();

            if(leaf && !node.isLeaf()) return false;

            if(node.left!=null){
                queue.offer(node.left);
            }else if(node.right!=null){
                return false;
            }

            if(node.right!=null){
                queue.offer(node.right);
            }else{
                leaf = true;
            }
        }
        return true;
    }

    //计算二叉树的高度，非递归
    public int heightNR(){
        if(root == null) return 0;
        Queue<Node<E>> queue = new LinkedList<>();
        int levelSize = 1;
        int height = 0;
        queue.offer(root);
        while(!queue.isEmpty()){
            Node<E> node = queue.poll();
            levelSize--;

            if(node.left!=null){
                queue.offer(node.left);
            }
            if(node.right!=null){
                queue.offer(node.right);
            }
            if(levelSize == 0){
                height++;
                levelSize = queue.size();
            }
        }
        return height;
    }

    //对外使用的遍历接口
    public static abstract class Visitor<E>{
        boolean stop;
        public abstract boolean visit(E element);
    }

    //前序,非递归  根 左 右
    public void preOrder(Visitor<E> visitor){
        if(visitor == null || root == null) return;
        Stack<Node<E>> stack = new Stack<>();
        stack.push(root); //将跟节点入队
        while(!stack.isEmpty()){
            Node<E> node = stack.pop();
            if(visitor.visit(node.element)) return;

            if(node.right!=null){
                stack.push(node.right);
            }

            if(node.left!=null){
                stack.push(node.left);
            }
        }
    }

    //中序遍历
    public void inOrder(Visitor<E> visitor){
        if(visitor == null || root == null) return;
        Stack<Node<E>> stack = new Stack<>();
        Node<E> node = root;
        while(true){
            if(node!=null){
                stack.push(node);
                node = node.left;
            }else if(stack.isEmpty()){
                return;
            }else{
                node = stack.pop();
                if(visitor.visit(node.element)) return;
                node = node.right;
            }
        }
    }

    //后序,非递归
    public void postOrder(Visitor<E> visitor){
        if(visitor == null || root == null) return;
        Node<E> prev = null; //记录上一次弹出的节点
        Stack<Node<E>> stack = new Stack<>();
        stack.push(root); //先将根节点入队
        while(!stack.isEmpty()){
            Node<E> top = stack.peek(); //先看看栈顶元素是谁
            //叶子节点或者上一次弹出的节点是现在栈顶元素的子节点
            if(top.isLeaf() || (prev!=null && prev.parent == top)){
                prev = stack.pop();
                if(visitor.visit(prev.element)) return;
            }else{
                if(top.right!=null){
                    stack.push(top.right);
                }

                if(top.left!=null){
                    stack.push(top.left);
                }
            }
        }
    }


    //层序遍历
    public void levelOrderTraversal(Visitor<E> visitor) {
        if (root == null || visitor == null) return;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            if (visitor.visit(node.element)) return;


            if (node.left != null) {
                queue.offer(node.left);
            }

            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }



    @Override
    public Object root() {
        return root;
    }

    @Override
    public Object left(Object node) {
        return ((Node<E>)node).left;
    }

    @Override
    public Object right(Object node) {
        return ((Node<E>)node).right;
    }

    @Override
    public Object string(Object node) {
        Node<E> myNode = (Node<E>)node;
        String parentString = "null";
        if(myNode.parent != null){
            parentString = myNode.parent.element.toString();
        }
        return myNode.element+"_p("+parentString+")";
        // return node;
    }
}
